type 'a graph_term = { nodes : 'a list; edges : ('a * 'a) list }

(* Normalize edge: put in canonical order to avoid duplicates *)
let normalize_edge (a, b) =
  if a <= b then (a, b) else (b, a)

(* Get all edges in normalized form *)
let normalized_edges edges =
  List.map normalize_edge edges

(* Get neighbors of a node in the graph *)
let neighbors graph node =
  let rec aux acc = function
    | [] -> acc
    | (u, v) :: rest ->
        let acc' =
          if u = node then v :: acc
          else if v = node then u :: acc
          else acc
        in
        aux acc' rest
  in
  aux [] graph.edges

(* Check if a list contains an element *)
let rec mem x = function
  | [] -> false
  | y :: ys -> x = y || mem x ys

(* Remove duplicates from a list (for edges) *)
let rec uniq = function
  | [] -> []
  | x :: xs -> x :: uniq (List.filter ((<>) x) xs)

(* Check connectivity using DFS *)
let is_connected graph =
  match graph.nodes with
  | [] -> true
  | start :: _ ->
      let rec dfs visited stack =
        match stack with
        | [] -> visited
        | node :: rest ->
            if mem node visited then
              dfs visited rest
            else
              let new_visited = node :: visited in
              let nbrs = neighbors graph node in
              let new_stack = nbrs @ rest in
              dfs new_visited new_stack
      in
      let reachable = dfs [] [start] in
      (* Check if all nodes are reachable *)
      List.for_all (fun node -> mem node reachable) graph.nodes

(* Check if a graph is a tree: connected and |E| = |V| - 1 *)
let is_tree graph =
  let n = List.length graph.nodes in
  let m = List.length graph.edges in
  if n = 0 then m = 0
  else if m <> n - 1 then false
  else is_connected graph

(* Main function: generate all spanning trees using backtracking *)
let s_tree graph =
  let n = List.length graph.nodes in
  if n = 0 then
    if graph.edges = [] then [{nodes = []; edges = []}] else []
  else if not (is_connected graph) then
    []  (* No spanning trees if not connected *)
  else
    let all_nodes = graph.nodes in
    let norm_edges = uniq (normalized_edges graph.edges) in

    (* Backtracking function:
       - current_nodes: nodes in current partial tree
       - current_edges: edges in current partial tree
       - remaining_edges: edges not yet considered (for optimization, but we'll consider all applicable)
    *)
    let rec backtrack current_nodes current_edges =
      if List.length current_nodes = n then
        (* Found a spanning tree *)
        [{ nodes = all_nodes; edges = current_edges }]
      else
        let candidates = 
          List.filter (fun (u, v) ->
            (mem u current_nodes && not (mem v current_nodes)) ||
            (mem v current_nodes && not (mem u current_nodes))
          ) norm_edges
        in
        (* Avoid using same edge twice *)
        let candidates = 
          List.filter (fun e -> not (mem e current_edges)) candidates
        in
        let trees = ref [] in
        List.iter (fun (u, v) ->
          let new_node = if mem u current_nodes then v else u in
          let new_nodes = new_node :: current_nodes in
          let new_edges = (u, v) :: current_edges in
          trees := (backtrack new_nodes new_edges) @ !trees
        ) candidates;
        !trees
    in
    (* Start from an arbitrary node *)
    let start = List.hd all_nodes in
    backtrack [start] [];;

let g = {nodes = ['a'; 'b'; 'c'; 'd'; 'e'; 'f'; 'g'; 'h'];
edges = [('a', 'b'); ('a', 'd'); ('b', 'c'); ('b', 'e');
          ('c', 'e'); ('d', 'e'); ('d', 'f'); ('d', 'g');
          ('e', 'h'); ('f', 'g'); ('g', 'h')]};;

let trees = s_tree g;;
let test1 = is_tree {nodes = ['a'; 'b'; 'c']; edges = [('a','b'); ('b','c')]};;
let test2 = is_tree {nodes = ['a'; 'b'; 'c']; edges = [('a','b'); ('b','c'); ('a','c')]};;
let test3 = is_connected g;;